#include <iostream>
#include <vector>
#include <sstream>
#include <fstream>
#include <cmath>
#include <cstdlib>

#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <string.h>
#include <map>
#include <set>
#include <stack>

using namespace std;


template<typename T>
T* mallocArray(int n) {
	T* arr = (T*)malloc(n * sizeof(T));
	return arr;
}
template<typename T>
void freeArray(T* arr) {
	if(arr != NULL){
        free(arr);
	}
}


typedef struct LinkNode{
	int index;
	LinkNode* next = NULL;
}LinkNode;

typedef struct Node{
	unsigned int data;
	LinkNode* first_neighbor = NULL;
}Node;

typedef struct Grap{
	int node_num;
	Node* nodes;
}Grap;


//string testFile = "data/data.txt";
//string testFile = "data/data1.txt";
string testFile = "data/test_data.txt";

//string resultFile = "projects/student/result.txt";
string resultFile = "result.txt";

int max_record_num = 300000;//不重复的账户个数应该不会超过280000吧,如果超过那就再乘以2
Grap grap;

typedef vector<unsigned int> Cycle;
set<Cycle> cycles3;
set<Cycle> cycles4;
set<Cycle> cycles5;
set<Cycle> cycles6;
set<Cycle> cycles7;

int* path;  //该数组用来保存当前遍历路径
int* visited; //该数组记录当前每个节点正在被遍历的情况

inline unsigned int parse(char** s){
	char *p = *s;
	unsigned int val = *(p++) - '0';
	while(*p != ','){
		val = 10*val + *(p++) - '0';
	}
	*s = p;
	return val;
}


void loadData_and_createGrap(){
	int fd = open(testFile.c_str(), O_RDONLY);
    int file_size = lseek(fd, 0, SEEK_END);
    char* p_map =(char*)mmap(NULL, file_size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);
	
	char *p = p_map;
	unsigned int a1, a2; //每行数据中的两个账户
	grap.nodes = mallocArray<Node>(max_record_num);//图中的总节点数不会超过max_record_num
	Node* nodes = grap.nodes;
	int node_num = 0;
	map<unsigned int, int> mapSite; //记录账户节点在数组中的位置
	LinkNode* neighbor, *q;
	int i, j;
	while(*p != '\0'){
		a1 = parse(&p);//或得该行数据中的第一个账户信息
		p++;
		a2 = parse(&p);//或得该行数据中的第二个账户信息
		i = mapSite[a1];//返回该账户在节点数组中的位置，若还没有在节点数组中，则默认返回0(map默认就是返回0)
		j = mapSite[a2];
		switch(i==0){
			case 1:
				mapSite[a1] = ++node_num;
				i = node_num-1;
				nodes[i].first_neighbor = NULL;
				nodes[i].data = a1;
				break;
			case 0:
				i--;
		}
		switch(j==0){
			case 1:
				mapSite[a2] = ++node_num;
				j = node_num-1;
				nodes[j].first_neighbor = NULL;
				nodes[j].data = a2;
				break;
			case 0:
				j--;
		}
		neighbor = (LinkNode*) malloc(sizeof(LinkNode));
		neighbor->index = j;
		neighbor->next = NULL;
		switch(nodes[i].first_neighbor == NULL){
			case 1:
				nodes[i].first_neighbor = neighbor;
				break;
			case 0:
				q = nodes[i].first_neighbor;
				while(q->next != NULL) q = q->next;
				q->next = neighbor;
		}
		
		while(*p != '\n'){p++;}
		p++;
	}
	grap.node_num = node_num;
	munmap(p_map, file_size);
}

void free_grap(Grap* g){
	Node* nodes = g->nodes;
	int node_num = g->node_num;
	LinkNode *p, *q;
	//释放为邻接链表分配的内存空间
	for(int i=0; i < node_num; i++){
		p = nodes[i].first_neighbor;
		while(p != NULL){
			q = p->next;
			free(p);
			p = q;
		}
	}
	//释放为图中的节点分配的内存
	freeArray(nodes);
}

bool handleCycle(Grap* g, int len){//测试找到的环是否满足要求
	Node* nodes = g->nodes;
	Cycle tmp;
	for(int i=0; i<len; i++){
		tmp.push_back(nodes[path[i]].data);
	}
	switch(len){
		case 3:
			cycles3.insert(tmp);//集合会自动排序,并去重
			break;
		case 4:
			cycles4.insert(tmp);
			break;
		case 5:
			cycles5.insert(tmp);
			break;
		case 6:
			cycles6.insert(tmp);
			break;
		case 7:
			cycles7.insert(tmp);
			break;
	}
	return true;
}

void dfs(Grap* g, int v, int dep){
	Node* nodes = g->nodes;
	LinkNode* p;
	int neighbor;
	visited[v] = 1;
	for(p = nodes[v].first_neighbor; p!=NULL; p = p->next){
		neighbor = p->index;
		if(nodes[neighbor].data > nodes[path[0]].data && visited[neighbor]==-1){
			if(dep>7) break;
			path[dep] = neighbor;
			dfs(g, neighbor, dep+1);
		}
		if(nodes[neighbor].data == nodes[path[0]].data){
			handleCycle(g, dep);
			break;
		}
	}
	visited[v] = -1;
	path[dep] = -1;
}

void getAllCycles(Grap* g){
	int i;
	int node_num = g->node_num;
	for(i=0; i < node_num; i++){
		visited[i] = -1;  //初始化为未遍历，-1表示未遍历
		path[i] = -1;  //path数组存放遍历路径
	}
	cout<<"begin find cycles..."<<endl;
	for(i=0; i < node_num; i++) {
		path[0] = i;
		if (g->nodes[i].first_neighbor!=NULL) dfs(g, i, 1);
		if(i%100 == 0) cout<<i<<'/'<<node_num<<endl;
	}
}

void saveResult(){
	cout<<"begin saving..."<<endl;
	ofstream fout(resultFile);
	int sz = cycles3.size()+cycles4.size()+cycles5.size()+cycles6.size()+cycles7.size();
	fout<<sz<<'\n';
	for(auto &x:cycles3){
		sz = x.size();
		fout<<x[0];
		for(int i=1;i<sz;i++)
			fout<<","<<x[i];
		fout<<'\n';
	}
	for(auto &x:cycles4){
		sz = x.size();
		fout<<x[0];
		for(int i=1;i<sz;i++)
			fout<<","<<x[i];
		fout<<'\n';
	}
	for(auto &x:cycles5){
		sz = x.size();
		fout<<x[0];
		for(int i=1;i<sz;i++)
			fout<<","<<x[i];
		fout<<'\n';
	}
	for(auto &x:cycles6){
		sz = x.size();
		fout<<x[0];
		for(int i=1;i<sz;i++)
			fout<<","<<x[i];
		fout<<'\n';
	}
	for(auto &x:cycles7){
		sz = x.size();
		fout<<x[0];
		for(int i=1;i<sz;i++)
			fout<<","<<x[i];
		fout<<'\n';
	}
}

int main(int argc, char* argv[]){
	
	clock_t startTime = clock();
	loadData_and_createGrap();
	clock_t endTime = clock();
	cout << "LoadData: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	//cout<<"max_account = "<<max_account<<endl;

	int node_num = grap.node_num;
	visited = mallocArray<int>(node_num);
	path = mallocArray<int>(node_num);  //该数组用来保存当前遍历路径
	
	startTime = clock();
	getAllCycles(&grap);
	endTime = clock();
	cout << "getAllCycle: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	
	freeArray(path);
	freeArray(visited);
	free_grap(&grap);
	
	startTime = clock();
	saveResult();
	endTime = clock();
	cout << "saveResult: " << (float)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	
	return 0;
}